package com.algorithm.ch1.cjm.string;

/**
 * 实现 strStr() 函数。
 * <p>
 * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
 * <p>
 * 示例 1:
 * <p>
 * 输入: haystack = "hello", needle = "ll"
 * 输出: 2
 * 示例 2:
 * <p>
 * 输入: haystack = "aaaaa", needle = "bba"
 * 输出: -1
 * 说明:
 * <p>
 * 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
 * <p>
 * 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
 */
public class StrStr {

    public static void main(String[] args) {

        System.out.println(new StrStr().strStr("a", "a"));

//        System.out.println("aaabb".indexOf("baba"));

    }

    /**
     * 第一版
     * T(n) = n - n1
     * f(n) = n
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {

        if(haystack == null || needle == null){
            return -1;
        }

        if(haystack.length() < needle.length()){
            return -1;
        }

        if(needle.length() == 0){
            return 0;
        }

        //需要匹配的第一个字符串
        char ch = needle.charAt(0);

        int length = needle.length();

        //开始位置
        int fromIndex = 0;

        while (fromIndex + length <= haystack.length()){

            fromIndex = haystack.indexOf(ch, fromIndex);

            if(fromIndex == -1){
                return -1;
            }

            if(fromIndex + length > haystack.length()){
                return -1;
            }

            String temp = haystack.substring(fromIndex, fromIndex + length);

            if(needle.equals(temp)){
                return fromIndex;
            }

            fromIndex++;
        }

        return -1;
    }

}
